//手写HashMap
/*
* */
public class MyHashMap<K, V> {
    //使用数组加链表来解决Hash冲突，这个当节点过多，可能存在某个node链表过长，优化就使用红黑树，避免O(n)复杂度
    private Node<K, V> [] table = new Node[16];
    //当前长度
    private int size = 0;

    public V put(K key, V value){
        int keyIndext = indexOf(key);
        Node<K, V> head = table[keyIndext];
        if(head == null){
            Node<K, V> node = new Node<>(key, value);
            table[keyIndext] = node;
            size++;
            resizeIfNecessary();
            return null;
        }
        while(true){
            //更新已经存在的节点值
            if(head.key.equals(key)){
                V oldValue = head.value;
                head.value = value;
                return oldValue;
            }
            if(head.next == null){
                Node<K, V> node = new Node<>(key, value);
                head.next = node;
                size++;
                resizeIfNecessary();
                return null;
            }
            head = head.next;
        }
    }

    public V get(K key){
        int keyIndext = indexOf(key);
        Node<K, V> head = table[keyIndext];
        while(head != null){
            if(head.key.equals(key)){
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K key){
        int keyIndext = indexOf(key);
        Node<K, V> head = table[keyIndext];
        if(head == null) return null;
        if(head.key.equals(key)){
            table[keyIndext] = head.next;
            size--;
            return head.value;
        }
        //不是头节点需要遍历整个链表
        Node<K, V> prev = head;
        Node<K, V> current = head.next;
        while(current != null){
            if(current.key.equals(key)){
                //找到了就需要将前驱节点指向下一个，当前节点值返回
                prev.next = current.next;
                size--;
                return current.value;
            }
            prev = prev.next;
            current = current.next;
        }
        return null;
    }

    //扩容
    private void resizeIfNecessary(){
        if(this.size < table.length * 0.75){
            return;
        }
        Node<K, V> [] newTable = new Node[table.length * 2];
        for(Node<K, V> head : this.table){
            if(head == null) continue;
            Node<K, V> current = head;
            while(current != null){
                //计算新的index
                int index = current.key.hashCode() & (newTable.length - 1);
                //判断新tableindex是否为空
                if(newTable[index] == null){
                    newTable[index] = current;
                    Node<K, V> next = current.next;
                    current.next = null;
                    current = next;
                } else {
                    //使用头插法，多线程环境下会出现自己指向自己，所以后面优化成尾插法
                    //但尾插法会需要遍历该链表，这也为后面转为红黑树所需要长度做铺垫
                    Node<K, V> next = current.next;
                    current.next = newTable[index];
                    newTable[index] = current;
                    current = next;
                }
            }
        }
        this.table = newTable;
    }


    private int indexOf(K key){
        //return key.hashCode() % table.length;
        //这有个更高效的 方法 & 当前长度减一
        return key.hashCode() & (table.length - 1);
    }
    public int size(){
        return size;
    }



    private static class Node<K, V>{
        K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

}
